Computer-implemented route planning methods have been developed which generate a route from a start location to a destination location.
Known route planning methods have a precomputation phase (ie: a computation phase prior to query time) in which map data is processed to form a graph data structure representing possible routes between locations. Costs may be assigned to arcs of the graph to apply weights based on the travel time between locations, and may take into account the distance between particular locations, the type of road, traffic conditions, and other factors which may affect travel time. Costs can alternatively or additionally be assigned to other parts of the graph, e.g: to nodes or subpaths.
Optimal routes may be calculated by way of a graph search algorithm on the weighted graph. Known graph search algorithms include Dijkstra's algorithm and the A* search algorithm, which compute a connected sequence of arcs from a source node to a target node such that the sum of the arc costs is minimal over all such paths.
More recently, speed-up algorithms such as the contraction hierarchies (CH) algorithm have been developed, in which shortest paths (called shortcuts) are precomputed to improve speed at query time. A problem with such speed-up algorithms is that it is necessary to have information regarding arc costs at precomputation time, which means that it is not possible to account for real-time traffic conditions.
It has been proposed to take real-time traffic data into account by way of a Dijkstra-based search at query time, with costs on the graph determined based on the real-time traffic data. However, this approach does not scale to large graphs, because the query computation time becomes unacceptable long.